419. 3n + 1 সমস্যা

নিচের অ্যালগোরিদমটা দেখি:

1. n এর মান ইনপুট নিই

2. n প্রিন্ট করি

3. যদি n = 1 হয় তাহলে থামি

4. যদি n বিজোড় হয় n = 3 * n + 1

5. অন্যথায় n = n / 2

6. 2 নম্বর ধাপে ফিরে যাই

ইনপুট হিসেবে 22 দিলে, নিচের অনুক্রমে সংখ্যাগুলো দেখাবে

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

ধারণা করা হয় যে, যেকোন পূর্ণসংখ্যা n এর জন্যে উপরের অ্যালগোরদিমটা এক সময় থামবে (1 প্রিন্ট করবে)। এটা খুব সহজ-সরল হলেও এখনও জানা যায় নি যে এই ধারণাটা সত্য কি না। তবে যেসব সব পূর্ণসংখ্যা n যেখানে 0 < n < 1,000,000, সেগুলোর জন্যে এর সত্যতা যাচাই করা হয়েছে (আসলে এর চেয়ে অনেক বড় সংখ্যার জন্যেও এটা সত্য)।

একটা পূর্ণসংখ্যা n দেওয়া হলে উপরের অ্যালগোরিদম কয়টা সংখ্যা প্রিন্ট করবে সেটা বের করা সম্ভব (1 টা সহ)। কোন একটা n এর জন্যে এটাকে বলা হয় n এর সাইকেল এর দৈর্ঘ্য। উপরের উদাহরণে 22 এর সাইকেল দৈর্ঘ্য হল 16।

দুটো সংখ্যা i আর j দেওয়া থাকবে। বের করতে হবে i থেকে j এর ভিতর সবগুলো সংখ্যার মধ্যে সর্বোচ্চ যে সাইকেল দৈর্ঘ্য পাওয়া যাবে সেটা।

ইনপুট

ইনপুটে অনেকগুলো i আর j এর জোড়া দেওয়া থাকবে, প্রত্যেক লাইনে এক জোড়া করে। সব সংখ্যাই হবে 1,000,000 এর কম অথবা সমান আর 0 এর চেয়ে বেশি। জোড়ার প্রথম সংখ্যাটি দ্বিতীয়টির চেয়ে বড় হতে পারে। ধরে নেওয়া যাবে যে কোন অবস্থাতেই কোন সংখ্যা (অ্যালগোরিদমের ভেতরে) 2³¹ – 1 এর বেশি হবে না।

আউটপুট

প্রতি জোড়া i এবং j এর জন্যে i এবং j দেখাতে হবে ইনপুটে যে ক্রমে দেওয়া আছে, এর পর i থেকে j এর ভিতর সবগুলো সংখ্যার মধ্যে সর্বোচ্চ যে সাইকেল দৈর্ঘ্য পাওয়া যাবে সেটা দেখাতে হবে। এই তিনটা সংখ্যা একটা করে স্পেস দিয়ে পাশাপাশি দেখাতে হবে।

উদাহরণ

ইনপুট

1 10

100 200

201 210

900 1000

আউটপুট

1 10 20

100 200 125

201 210 89

900 1000 174

সমাধান

প্রাথমিক সমস্যা - সাইকেল

অ্যালগোরিদম অ্যানালাইসিস

ধরি cycle_length নামের একটা ফাংশন আছে যেটা ক্যালকুলেট করে n এর মানের জন্যে সাইকেল দৈর্ঘ্য কত। i থেকে j পর্যন্ত সব মানের জন্যে সাইকেল দৈর্ঘ্য বের করে সবচেয়ে বড়টা প্রিন্ট করি। cycle_length ফাংশনে যতক্ষ্ণ পর্যন্ত ১ না হচ্ছে ততক্ষণ পর্যন্ত লুপ চালিয়ে যাই।

অ্যালগোরিদম বাস্তবায়ন

int cycle_length(int n)

{

int cnt;

for(cnt = 1; n != 1; cnt++)

n = (n % 2) ? 3 * n + 1: n / 2;

return cnt;

}

check ফাংশনটা সর্বোচ্চ সাইকেলের দৈর্ঘ্য বের করে

int check(int i,int j)

{

int mx = 0;

for(; i <= j; i++)

mx = max (mx, cycle_length(i));

return mx;

}

main এ ইনপুট নিই। ইনপুটে যদি i যদি j এর চেয়ে বড় হয়, সেক্ষেত্রে i আর j এর মান অদল বদল করে নেব।

while (scanf("%d %d",&i,&j) == 2)

{

itemp = i; jtemp = j;

if (i > j) tmp = i, i = j, j = tmp;

printf("%d %d %d\n",itemp, jtemp, check(i,j));

}